package dichotomy.find.mid.from.sortedarray;
/**
 * @Date 2020/2/5
 * @author 王光浩
 * @Description 给定两个排序后的数组，找出将这个两个数组合并后的中位数。要求时间复杂度不能超过O（log（m+n））
 * @Thinking 使用暴力法。使用for循环来查找。
 *           时间复杂度O（（m+n）/2）
 */
public class MyMethodOne {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1=nums1.length;
        int len2=nums2.length;
        int target=(len1+len2)%2==0?(len1+len2)/2:(len1+len2)/2+1;   //遍历结束的条件
        int count=0;
        if(len1==0) return len2%2==0?(double)(nums2[len2/2]+nums2[len2/2+1])/2:(double)nums2[len2/2+1];
        if(len2==0) return len1%2==0?(double)(nums1[len1/2]+nums1[len1/2+1])/2:(double)nums1[len1/2+1];
        //遍历两个数组，但遍历的数据总数为两个数组长度的1/2时，遍历结束
        int i,j;
        for(i=0,j=0;i<len1 && j<len2;) {
        	if(nums1[i]<nums2[j]) {
        		count++;
        		if(count==target) {
        			if(count%2==0) {   //数据总数为偶数
        				if(i==len1-1)return (double)(nums1[i]+nums2[j])/2;
        				else if(nums1[i+1]<nums2[j])return (double)(nums1[i]+nums1[i+1])/2;
        				else return (double)(nums1[i]+nums2[j])/2;
        			}
        			else return (double)nums1[i];  //数据总数为奇数
        		}
            	i++;
        	}
        	else {
        		count++;
        		if(count==target) {
        			if(count%2==0) {  //数据总数为偶数
        				if(j==len2-1)return (double)(nums1[i]+nums2[j])/2;
        				else if(nums2[j+1]<nums1[i])return (double)(nums2[j]+nums2[j+1])/2;
        				else return (double)(nums1[i]+nums2[j])/2;
        			}
        			else return (double)nums2[j];  //数据总数为奇数
        		}
            	j++;
        	}
        }
        if(i==len1) {
        	j+=(target-count);
        	if(target%2==0) return (double)(nums2[j]+nums2[j+1])/2;
        	else return (double)nums2[j];
        }
        else {
        	i+=(target-count);
        	if(target%2==0)return (double)(nums1[i]+nums1[i+1])/2;
        	else return (double)nums1[i];
        }
    }
}
